package com.dmall.play.interview.chapter07;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Leetcode113V2 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode {" +
                    "val=" + val +
                    '}';
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        dfs(root, sum, one, res);
        return res;
    }

    private void dfs(TreeNode node, int sum, List<Integer> one, List<List<Integer>> res) {
        List<Integer> oneCopy = new ArrayList<>(one);
        if (node != null) {
            oneCopy.add(node.val);
            if (node.left == null && node.right == null) {
                if (node.val == sum) {
                    res.add(oneCopy);
                }
            } else {
                dfs(node.left, sum - node.val, oneCopy, res);
                dfs(node.right, sum - node.val, oneCopy, res);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);

        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        Leetcode113V2 leetcode113 = new Leetcode113V2();
        System.out.println(leetcode113.pathSum(root, 22));
    }
}
